/* An H-number h is represented by h = 4*k + 1, where k >= 0. We use a sieving
 * method to find the smallest H-prime, p that divides each H-number h in the
 * given range, and store the quotient h / p for that number. Next We test
 * whether a given H-number is semi-prime by testing whether h / p is H-prime.
 */

#include <stdio.h>
#include <memory.h>

#define MAX_K       250000
#define SQRT_MAX_K  249

static int factor[MAX_K+1]; /* factor[k] = H(k) / first divisor of H(k) */
static int count[MAX_K+1];  /* count[k] = number of semi-primes in [0,k] */

/* Returns k such that 4*k+1 == (4*i+1)*(4*j+1). */
static int hmul(int i, int j)
{
    return 4*i*j+i+j;
}

int main()
{
    int p, k, h, m;

    /* Use sieve method to find the smallest prime factor of each H-number. */
    memset(factor, 0, sizeof(factor));
    for (p = 1; p <= SQRT_MAX_K; p++)
    {
        if (factor[p] == 0) /* 4*p+1 is H-prime */
        {
            int q = p;
            for (k = hmul(p, p); k <= MAX_K; k += (4*p+1))
                factor[k] = q++;
        }
    }

    /* Count the number of semi-primes between 1 and k inclusive. */
    count[0] = m = 0;
    for (k = 1; k <= MAX_K; k++)
    {
        p = factor[k];
        if (p != 0 && factor[p] == 0)
            m++;
        count[k] = m;
    }

    /* Read H-numbers and check semi-primality. */
    while (scanf("%d", &h) == 1 && h > 0)
    {
        k = (h - 1) / 4;
        printf("%d %d\n", h, count[k]);
    }
    return 0;
}
